#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

class Solution {
  public:
    vector<vector<int>> fourSum(vector<int> &nums, int target) {
        vector<vector<int>> ans;
        int n = nums.size();
        sort(nums.begin(), nums.end());
        int i = 0, j = 1, k = 2;
        for (k = 2; k < n - 1;) {
            for (j = 1; j < k;) {
                for (i = 0; i < j;) {
                    int res = target - nums[i] - nums[j] - nums[k];
                    if (res < nums[k])
                        break;
                        cout<<i<<" "<<j<<" "<<k<<endl;
                    int from = k + 1, to = n - 1, mid = (from + to) / 2;
                    while (from <= to) {
                        mid = (from + to) / 2;
                        if (nums[mid] == res) {
                            vector<int> tmp = {nums[i], nums[j], nums[k], res};
                            ans.push_back(tmp);
                            break;
                        } else if (nums[mid] <= res) {
                            from = mid + 1;
                        } else if (nums[mid] > res) {
                            to = mid - 1;
                        }
                    }
                    do { i++; } while (i < j && nums[i - 1] == nums[i]);
                }
                do { j++; } while (j < k && nums[j - 1] == nums[j]);
            }
            do { k++; } while (k < n - 1 && nums[k - 1] == nums[k]);
        }
        return ans;
    }
};

int main() {
    vector<int> inp = {1, 0, -1, 0, -2, 2};
    Solution s;
    s.fourSum(inp, 0);
}